Home | | Latest | About | Random
# Note 1. Solving a system of linear equations using elementary row operations.
We like to solve a system of linear equations with $n$ equations in $k$ variables $x_{1}, x_{2}, \ldots,x_{k}$, where $$
\left\{\begin{align*}
a_{11} x_{1} + a_{12} x_{2} + \cdots + a_{1k}x_{k} &= b_{1} \\
a_{21} x_{1} + a_{22} x_{2} + \cdots + a_{2k}x_{k} &= b_{2} \\
& \vdots \\
a_{n1} x_{1} + a_{n2} x_{2} + \cdots + a_{nk}x_{k} &= b_{n}
\end{align*}\right.
$$ where each $a_{ij}$, $b_{\ell}$ are *scalars* (numbers from a so-called *field*). We will refer to each equation by its row. For example, row 2 to mean the second equation in the system.
How do we do this systematically?
---
The idea is to solve an *equivalent system*, another linear system of equations but with the same solutions. This is because some linear system *appears* to be simpler to solve.
An example of a linear system that is simpler to solve is one presented in *echelon form* (an upper-triangular shape, or staircase). For example,
$$
\left\{\begin{matrix}
3x &+& 2y& -& z &=& 0 &\ldots (R1) \\
&& 4y &+&2z &=& 4 &\ldots (R2)\\
&& && 5z &=& 1 &\dots (R3)
\end{matrix}
\right.
$$
Here the rows are labeled as $(R1), (R2),(R3)$, Note that if a system looks like above, then we can perform **back-substitution** to solve for each variable. Indeed:
- From $(R3)$ we can solve for $z =\frac{1}{5}$
- From $(R2$), and using the value of $z$ we found, we have $y = \frac{1}{4}(4-2z) =\frac{9}{10}$.
- From $(R1)$, and using the values of $z$ and $y$ we found, we have $x = \frac{1}{3}(z-2y) = -\frac{8}{15}$.
$$
\fbox{$\therefore \,\,\, (x,y,z) = (-\frac{8}{15}, \frac{9}{10}, \frac{1}{5})$. }
$$
---
But if our system is not in echelon form, what do we do? The idea is to apply a sequence of **elementary row operations** to the equations such that
- The solutions remain unchanged after each operation, and
- The resulting linear system becomes an echelon form.
These operations are necessarily *reversible*, that is, we can undo each operation.
---
There are **three** such elementary row operations that we can perform.
- **Scale by nonzero scalar.** Take a row and multiply by a nonzero scalar $k$. A notation we will write for this operation is $$
(Ri) \to k (Ri)
$$to denote the $i$-th row is now $k$ times the original $i$-th row. for $k\neq 0$.
- **Swap a pair of rows.** Take two different rows, and exchange their positions. A notation we will write for this operation is $$
(Ri) \leftrightarrow (Rj)
$$to denote the $i$-th row is now in the $j$-th row position, and simultaneously the $j$-th row is now in the $i$-th row position.
- **Replacement by adding a scalar multiple of another row.** Fix a row, and add to it a scalar multiple of a *different* row. A notation we will write for this operation is $$
(Ri) \to (Ri) + k(Rj)
$$to denote the $i$-th row is now added by $k$ multiple of the $j$-th row, and this result is placed at the $i$-th row. Here we must have $j\neq i$. (But $k$ can be zero this time. Think about why.)
Each of these elementary row operation preserves the solution set of the original linear system.
---
Here is an example. Consider the linear system for the variables $x,y,z$ where $$
\begin{matrix}
\left\{
\begin{matrix}
3x & + & 2y & - & z & = & 1 \\
x & + & y & + & 2z & = & 2 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. \\
\Bigg\downarrow (R2)\leftrightarrow (R1) \\
\left\{
\begin{matrix}
x & + & y & + & 2z & = & 2 \\
3x & + & 2y & - & z & = & 1 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. \\
\Bigg\downarrow (R2)\to (R2) - 3(R1) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. \\
\Bigg\downarrow (R3)\to (R3) - 2(R1) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
& -& 2y & - & z & = & -1
\end{matrix}
\right. \\
\Bigg\downarrow (R3)\to (R3) - 2(R2) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
& & & + &13 z & = & 9
\end{matrix}
\right. \\
\end{matrix}
$$ It is now in echelon form! Now we can perform back-substitution to find the variables starting from $z = \frac{9}{13}$, then $y = 5 - 7z = 5 - \frac{63}{13} = \frac{2}{13}$, and finally $x = 2-y-2z = 2- \frac{2}{13} - \frac{18}{13}=\frac{6}{13}$.
So, we have obtained the solution $$
(x,y,z) = ( \frac{6}{13} , \frac{2}{13}, \frac{9}{13} ).
$$ to the echelon form system. And since the elementary row operations are not supposed to change the solution, this is also the solution to the original problem!
---
Note when producing an equivalent system by above procedure, or **algorithm**, it is commonly called **Gaussian elimination**, or **Gauss-Jordan elimination**. And observe how we work from left to right, column by column by eliminating the variables beneath one variable, and then move to the next column. Doing it this way systematically will produce an echelon form.
---
Another observation we can make. Note when we perform these operations, we *organize the same variables in the same column*. This way we are organized and systematic, and we can just work with the coefficients. If we fix an order of the variables, then we can in fact organize the problem as an **augmented matrix** (which is just a table of numbers), where we record just the coefficients of the linear system, and interpret what it means at the end.
For example, by choosing the first column to denote the coefficients in front of $x$, the second column to denote the coefficients in front of $y$, and the third column to denote the coefficients in front of $z$, we have
$$
\begin{matrix} &&x\,\,\,\,\,\, y \,\,\,\,\,\,\,z\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\\
\left\{
\begin{matrix}
3x & + & 2y & - & z & = & 1 \\
x & + & y & + & 2z & = & 2 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. & \cdots & \begin{bmatrix}
3& 2 & - 1& \vdots & 1 \\
1 & 1 & 2 & \vdots & 2 \\
2 & 0 & 3 & \vdots & 3
\end{bmatrix}\\
\Bigg\downarrow (R2)\leftrightarrow (R1) \\
\left\{
\begin{matrix}
x & + & y & + & 2z & = & 2 \\
3x & + & 2y & - & z & = & 1 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. & \cdots & \begin{bmatrix}
1& 1 & 2& \vdots & 2 \\
3 & 2 & -1 & \vdots & 1 \\
2 & 0 & 3 & \vdots & 3
\end{bmatrix}\\
\Bigg\downarrow (R2)\to (R2) - 3(R1) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
2x & & & + & 3z & = & 3
\end{matrix}
\right. & \cdots & \begin{bmatrix}
1& 1 & 2& \vdots & 2 \\
0 & -1 & -7 & \vdots & -5 \\
2 & 0 & 3 & \vdots & 3
\end{bmatrix}\\
\Bigg\downarrow (R3)\to (R3) - 2(R1) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
& -& 2y & - & z & = & -1
\end{matrix}
\right. & \cdots & \begin{bmatrix}
1& 1 & 2& \vdots & 2 \\
0 & -1 & -7 & \vdots & -5 \\
0 & -2 & -1 & \vdots & -1
\end{bmatrix}\\
\Bigg\downarrow (R3)\to (R3) - 2(R2) \\
\left\{ \begin{matrix}
x & + & y & + & 2z & = & 2 \\
& - & y & - & 7z & = & -5 \\
& & & + &13 z & = & 9
\end{matrix}
\right. & \cdots & \begin{bmatrix}
1& 1 & 2& \vdots & 2 \\
0 & -1 & -7 & \vdots & -5 \\
0 & 0 & 13 & \vdots & 9
\end{bmatrix}\\
\end{matrix}
$$
This reduces the amount of copying symbols unnecessarily and codifies the process neatly, **provided that we organize the variables in the same columns in the first place.**
---
Ok, but why do we care? Well, many problems are linear systems in disguise. And once we recognize that it is one, we can apply above **algorithm** that is Gaussian elimination to solve it. This is especially fruitful when there are a lot of variables. Mathematically speaking, above algorithm is essentially the "fastest" general way of solving linear systems (unless we have special cases).
---
Here is an example.
Suppose a sick rabbit requires 100mg of vitamin A and 70mg of vitamin B each day to survive. However at your disposal are some medicine that contains a mixture of both, where
- 1 gram of medicine $\alpha$ contains 10mg of vitamin A and 15mg of vitamin B.
- 1 gram of medicine $\beta$ contains 20mg of vitamin A and 5mg of vitamin B.
How much of each medicine should you prescribe to this rabbit to meet its daily requirement to survive?
Answer.
Suppose we prescribe $x$ grams of medicine $\alpha$ and $y$ grams of medicine $\beta$. Then, the rabbit would be obtaining $$
(10 x + 20 y) \text{\,\ mg of vitamin A}
$$and $$
(15 x + 5 y) \text{\,\,mg of vitamin B}
$$
Since the rabbit needs 100mg vitamin A and 70mg vitamin B per day to survive, we set up the linear system of equation $$
\begin{align*}
10x+20y = 100 \\
15x +5y = 70
\end{align*}
$$
We can set up an augmented matrix (first column is $x$ and second column $y$) and perform Gaussian elimination
$$
\begin{bmatrix}
10 & 20 & \vdots & 100 \\
15 & 5 & \vdots & 70
\end{bmatrix}
\xrightarrow[(R2)\to \frac{1}{5} (R2)]{(R1)\to \frac{1}{10} (R1)} \begin{bmatrix}
1 & 2 & \vdots & 10 \\
3 & 1 & \vdots & 14
\end{bmatrix}
$$
$$
\xrightarrow{(R2)\to(R2)-3(R1)}\begin{bmatrix}
1 & 2 & \vdots &10 \\
& -5 & \vdots &-16
\end{bmatrix}
$$which we can back-substitute and get $y=\frac{16}{5}$ and $x = 10 - 2y = 10-\frac{32}{5} = \frac{18}{5}$. (Note, when we get comfortable, we **omit entries** that are zeros, to simplify writing. But do it to taste and only when it is clear. Do not do this when it is not clear.)
In other words, the rabbit should receive $\frac{18}{5} = 3.6$ grams of medicine $\alpha$ and $\frac{16}{5} = 3.2$ grams of medicine $\beta$.
////